#include <iostream>
#include <cstdio>
#include <stack>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;
class Solution {
public:
    int LISdp(vector<int>& arr){
        int len=arr.size();
        if(0==len){return 0;}
        vector<int> dp(len+1,1);
        int mexlen=1;
        for(int i=1;i<len;i++){
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]){
                    dp[i]=max(dp[i],dp[j]+1);
                    mexlen=max(mexlen,dp[i]);
                }
            }
        }

        return mexlen;
    }   
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // write code here
        
    
    }
};


int main(){
    Solution s;
    vector<int> v={2,1,5,3,6,4,8,9,7};
    cout << s.LISdp(v) <<endl;


    return 0;
}